class Solution {
    /**
     * 假设我们要找的是a b, 则a!=b --> a b必有一位不相同
     * 即a,b的异或x 必有一位为1
     * 则遍历nums时 我们可以通过 num&binaryIndex&num来进行分组
     * 使得a b分开
     * 
     * 坑点1: (num & binaryIndex)的分组情况应该为【0】【1,2,3,4...】而不是【0】【1】
     */
    public int[] singleNumbers(int[] nums) {
        // x为a,b异或和
        int x = 0;
        for (int num : nums) {
            x ^= num;
        }

        // x必有一位为1 我们找到最右边的即可
        int binaryIndex = 1;
        while ((x & binaryIndex) == 0) {
            binaryIndex <<= 1;
        }

        int a = 0, b = 0;
        for (int num : nums) {
            // arr1: [a,1,1,2,2]
            if ((num & binaryIndex) == 0)
                a ^= num;
                // arr2: [b,3,3]
            else
                b ^= num;
        }
        return new int[]{a, b};
    }
}